This application claims the benefit of a Japanese Patent Application No.2001-126558 filed Apr. 24, 2001, in the Japanese Patent Office, the disclosure of which is hereby incorporated by reference.
1. Field of the Invention
The present invention generally relates to image compression apparatuses, image expansion apparatuses, image forming apparatuses, image compression methods, image expansion methods and storage media, and more particularly to an image compression apparatus, image expansion apparatus, image compression method and image expansion method which are suited for a memory saving mechanism which saves a required frame buffer capacity, to an image forming apparatus which employs such image compression and image expansion methods, and to a computer-readable storage medium which stores a program for causing a computer to carry out such image compression and image expansion methods.
2. Description of the Related Art
Image data compression techniques are used for the purposes of reducing the memory capacity required to hold the image data and for reducing a transmission time of the image data.
As methods of compressing binary image data, the run length coding of the first order compression, MH (Modified Huffman) coding used in facsimile machines, and the JBIG (Joint Bi-level Image experts Group) which is an international standard of the second order compression system are well known. In addition, a modification of the MH coding is proposed in a Japanese Laid-Open Patent Application No.9-65147, so as to improve the compression rate and the processing speed. According to the coding system proposed in the Japanese Laid-Open Patent Application No.9-65147, the run lengths of the immediately preceding black and white are stored when carrying out the MG coding, and a predetermined iterative code is generated when a run length of a certain color matches the immediately preceding run length.
According to the coding systems described above, it is possible to obtain a high compression rate with respect to particular image data, but it is difficult to obtain a sufficiently high compression rate with respect to image data in which the color frequently changes at a short period.
In addition, the JBIG uses for the entropy coding a QM coder which is an arithmetic coder. For this reason, there are problems in that the hardware cost of a context memory and a line memory for creating the context is high, and that it is difficult to realize a high-speed operation.
On the other hand, according to the coding system proposed in the Japanese Laid-Open Patent Application No.9-65147, the compression rate is improved only in a case where the amount of data of the code word when the run lengths match is sufficiently small compared to the amount of data of the code word when the run lengths do not match. However, since allocating a short code word by the iterative code relatively increases the length of the code word of the run lengths which do not match, there is a problem in that it is difficult to obtain a code set having a sufficiently high compression rate with respect to the image data in which the color frequently changes at a short period. In addition, since the code set used in the Japanese Laid-Open Patent Application No.9-65147 is similar to the MH code, a large number of gates are required in order to process the plurality of bits, and it is difficult to expect high-speed processing using parallel processing.
A coding method for solving this problem is proposed in a Japanese Laid-Open Patent Application No.2000-217005. According to this proposed coding method, a numeric sequence of the alternate run lengths of every color obtained by scanning the image data is converted into a predetermined code sequence and output. When a predetermined run length is input, this coding methods sets a case where this run length matches an immediately preceding run length of the same color as a matching phenomenon, and sets a case where this run length does match the immediately preceding run length of the same color as a non-matching phenomenon. A number of consecutive matching phenomena is set as an iterative number. An iterative code corresponding to the iterative number is generated when the generation of the matching phenomenon or the consecutive non-matching phenomena occurs. A code which indicates the value of the run length is generated when the non-matching phenomenon is generated.
In addition, systems of compressing and expanding the run length code are proposed in a Japanese Laid-Open Patent Application No.7-236065. According to the proposed compressing and expanding systems, a 1-bit comparison is made for every one clock and the run length is counted up or, a matching of the same run length values is made, to realize a high-speed compression and expansion.
However, when these compressing and expanding systems are employed, the coded data may have a size greater than the original data, depending on the image data. For this reason, a system having an image compression apparatus must be provided with a memory having a memory capacity which takes into account the worst case for the compression rate, that is, a case where the amount of data increases due to the compression. As a result, there are problems in that the cost of the memory increases due to the need to provide the memory capacity for the worst case, and the processing speed deteriorates because of the increased memory accesses.
Japanese Laid-Open Patent Applications No.5-183760 and No.7-264417 propose systems which prevent the amount of data from increasing when compressed, by comparing the sizes of the coded data and the original data for every line, and storing the original data in a memory if the size of the coded data exceeds the size of the original data.
Furthermore, Japanese Laid-Open Patent Applications No.9-248943 and No.10-117289 propose systems which prevent the amount of data from increasing when compressed, by comparing the size of the coded data and the original data for every block instead of every line, and storing the original data in the memory if the size of the coded data exceeds the size of the original data.
But the systems described above require a line memory for storing the original data and the compressed data in units of lines or, a block memory for storing the original data and the compressed data in units of blocks, thereby increasing the cost for the required memory. Moreover, the image data compression must be made by sectioning the image data in units of lines or blocks. Consequently, even the image data of a blank which extends for several lines is compressed to the coded data which is made up of the initial data and the length of the data, for every line, for example, to thereby deteriorate the compression rate.